Tri par insertion

Principe :

On trie les éléments un par un, en prenant chaque élément et en le plaçant à la bonne position parmi ceux déjà triés.
À chaque itération, on prend un élément de la partie non triée et on l’insère à la bonne position dans la partie triée.

Complexité :

• Meilleur cas : O(n) (déjà trié)
• Pire et moyen cas : O(n²)
• Mémoire : O(1) (tri en place)

Code :

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];   // L'élément courant à placer
        int j = i - 1;      // On regarde l'élément à gauche

        // Tant que l'élément à gauche est plus grand, on le décale d'une case à droite
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // Décale l'élément vers la droite
            j--;                 // Regarde encore plus à gauche
        }
        // On a trouvé la bonne place : on insère l'élément
        arr[j + 1] = key;
    }
}

Exemple pas à pas avec [5, 3, 8, 1, 4]

On parcourt le tableau de gauche à droite. Pour chaque élément, on le recule vers la gauche jusqu'à sa bonne position.

Étape	Élément pris (key)	Action	Résultat
Départ	—	Le premier élément est déjà "trié" seul	[5, 3, 8, 1, 4]
i=1	key = 3	3 < 5 → on décale 5 à droite, on place 3	[3, 5, 8, 1, 4]
i=2	key = 8	8 > 5 → rien à décaler, on place 8	[3, 5, 8, 1, 4]
i=3	key = 1	1 < 8, 1 < 5, 1 < 3 → on décale tout, on place 1 au début	[1, 3, 5, 8, 4]
i=4	key = 4	4 < 8, 4 < 5 → on décale 8 et 5, on place 4 après 3	[1, 3, 4, 5, 8] ✓

Détail de l'étape i=3 (la plus importante) :

Main triée : [3, 5, 8]   key = 1
             [3, 5, 8, 8]   ← on a décalé 8
             [3, 5, 5, 8]   ← on a décalé 5
             [3, 3, 5, 8]   ← on a décalé 3
             [1, 3, 5, 8]   ← on insère 1 à la position j+1 = 0

Astuce mentale : pour chaque élément, tu le recules vers la gauche tant qu'il est plus petit que son voisin, jusqu'à ce qu'il soit à sa bonne position.

À noter :

• Excellent pour illustrer le tri étape par étape
• Facile à tracer à la main

Youtube

https://www.youtube.com/watch?v=JU767SDMDvA

Comparatif

Tri	Complexité moyenne	Mémoire
Insertion Sort	O(n²)	O(1)
Heap Sort	O(n log n)	O(1)
Tri indirect	O(n log n)	O(n)